package com.fan.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 138. 复制带随机指针的链表
 *
 * @author ZhangFan
 * @since 2021/7/22 下午 11:13
 */
public class Question138 {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        List<Node> list = new ArrayList<>();
        List<Node> listCopy = new ArrayList<>();
        list.add(head);
        Node headCopy = new Node(head.val);
        listCopy.add(headCopy);
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
            list.add(temp);
            Node tempCopy = new Node(temp.val);
            listCopy.get(listCopy.size() - 1).next = tempCopy;
            listCopy.add(tempCopy);
        }
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).random == null) {
                continue;
            }
            int index = list.indexOf(list.get(i).random);
            listCopy.get(i).random = listCopy.get(index);
        }
        return headCopy;
    }
}
